package xyf.p05.heap_trie;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * ClassName: P0973_NearestK
 * Description:
 * Author: xyf
 * Date: 9/23/22 9:03 PM
 * Version: 1.0
 **/
public class P0973_NearestK
{
    class Point
    {
        int x;
        int y;

        Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

    public int[][] kClosest(int[][] points, int k)
    {
        PriorityQueue<Point> minQueue = new PriorityQueue<>(new Comparator<Point>()
        {
            @Override
            public int compare(Point o1, Point o2)
            {
                return (o2.x * o2.x + o2.y * o2.y) - (o1.x * o1.x + o1.y * o1.y);
            }
        });

        for (int i = 0; i < points.length; i++)
        {
            if (minQueue.size() < k)
            {
                minQueue.offer(new Point(points[i][0], points[i][1]));
            }
            else
            {
                Point p = minQueue.peek();
                if ((points[i][0] * points[i][0] + points[i][1] * points[i][1]) < (p.x * p.x + p.y * p.y))
                {
                    minQueue.poll();
                    minQueue.offer(new Point(points[i][0], points[i][1]));
                }
            }
        }

        int[][] res = new int[k][2];
        for (int i = 0; i < res.length; i++)
        {
            Point p = minQueue.poll();
            res[i][0] = p.x;
            res[i][1] = p.y;
        }
        return res;
    }
}